package sort;

/**
 * 堆排序 O(NlogN)
 *             0
 *          /    \
 *        1       2
 *      /  \     /  \
 *    3     4   5    6
 *   / \   /
 *  7  8  9
 */
public class HeapSort {

    //堆排序
    public static void heapSort(int[] arr) {
        //1.先将数组进行heapify调整为最大堆
        //从最后一个非叶子节点的位置向上进行siftDown操作
        for(int i = (arr.length - 1 - 1) / 2; i >= 0; i--){
            siftDown(arr, i, arr.length - 1);
        }
        //此时，堆顶元素就是最大的元素
        //交换堆首尾元素，使最大值放置到后面
        //再让前面的数进行下沉操作
        for(int j = arr.length - 1; j > 0; j--){
            swap(arr, 0, j);
            siftDown(arr, 0, j - 1);
        }
    }
    //下沉操作,对索引从i到j的元素进行下沉
    private static void siftDown(int[] arr, int i, int j) {
        //先判断索引为i的元素有没有孩子
        while(2 * i + 1 <= j){
            //此时一定有左孩子
            int maxValIndex = 2 * i + 1;
            //再判断有没有右孩子,并判断哪个孩子的值大
            if(2 * i + 2 <= j && arr[2*i+2] > arr[2*i+1]){
                maxValIndex ++;
            }
            if(arr[i] < arr[maxValIndex]){
                swap(arr, i, maxValIndex);
                i = maxValIndex;
            }else{
                break;
            }
        }
    }
    //交换索引位置的元素值
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] + arr[j] - (arr[j] = arr[i]);
    }
}
